<html>
 <head>
  <meta charset="UTF-8">
 </head>
 <body>
  <h1 data-lake-id="TQRhI" id="TQRhI"><span data-lake-id="u4cdebc43" id="u4cdebc43">典型回答</span></h1>
  <p data-lake-id="u082f62dd" id="u082f62dd"><br></p>
  <p data-lake-id="ub2cd9809" id="ub2cd9809"><span data-lake-id="uf5392ff4" id="uf5392ff4">雪花算法（Snowflake）雪由Twitter研发的的一种分布式ID生成算法，它可以生成全局唯一且递增的ID。它的核心思想是将一个64位的ID划分成多个部分，每个部分都有不同的含义，包括时间戳、数据中心标识、机器标识和序列号等。</span></p>
  <p data-lake-id="udca83ab3" id="udca83ab3"><span data-lake-id="ue3b1b138" id="ue3b1b138">​</span><br></p>
  <p data-lake-id="uaf7e4486" id="uaf7e4486"><span data-lake-id="u84cbc65e" id="u84cbc65e">具体来说，雪花算法生成的ID由以下几个部分组成：</span></p>
  <ol list="u805d88ef">
   <li fid="uc8087f95" data-lake-id="ub94fc4ea" id="ub94fc4ea"><span data-lake-id="uf1ecd64c" id="uf1ecd64c">符号位（1bit）：预留的符号位，始终为0，占用1位。</span></li>
   <li fid="uc8087f95" data-lake-id="u116a316a" id="u116a316a"><span data-lake-id="u7ea26bde" id="u7ea26bde">时间戳（41bit）：精确到毫秒级别，41位的时间戳可以容纳的毫秒数是2的41次幂，一年所使用的毫秒数是：365 * 24 * 60 * 60 * 1000，算下来可以使用69年。</span></li>
   <li fid="uc8087f95" data-lake-id="uc04a9a6c" id="uc04a9a6c"><span data-lake-id="udae3d0bf" id="udae3d0bf">数据中心标识（5bit）：可以用来区分不同的数据中心。</span></li>
   <li fid="uc8087f95" data-lake-id="u85a1ba15" id="u85a1ba15"><span data-lake-id="u6a5b4e36" id="u6a5b4e36">机器标识（5bit）：可以用来区分不同的机器。</span></li>
   <li fid="uc8087f95" data-lake-id="ue3e4a391" id="ue3e4a391"><span data-lake-id="u0476f629" id="u0476f629">序列号（12bit)：可以生成4096个不同的序列号。</span></li>
  </ol>
  <p data-lake-id="u972b2078" id="u972b2078"><span data-lake-id="ud994f7e2" id="ud994f7e2">​</span><br></p>
  <p data-lake-id="ufed56843" id="ufed56843"><img src="https://cdn.nlark.com/yuque/0/2023/png/5378072/1678710013075-c6740ef1-8af3-4eef-a3f0-a9fd19114b04.png?x-oss-process=image%2Fwatermark%2Ctype_d3F5LW1pY3JvaGVp%2Csize_28%2Ctext_SmF2YSA4IEd1IFA%3D%2Ccolor_FFFFFF%2Cshadow_50%2Ct_80%2Cg_se%2Cx_10%2Cy_10"></p>
  <p data-lake-id="u1cc08ca1" id="u1cc08ca1"><span data-lake-id="ue25066cb" id="ue25066cb">​</span><br></p>
  <p data-lake-id="uf0c8964a" id="uf0c8964a"><span data-lake-id="u0d490780" id="u0d490780">基于以上结构，雪花算法在唯一性保证方面就有很多优势：</span></p>
  <p data-lake-id="ucf5d6328" id="ucf5d6328"><span data-lake-id="uef520045" id="uef520045">​</span><br></p>
  <p data-lake-id="u544d2f58" id="u544d2f58"><span data-lake-id="u26b85e86" id="u26b85e86">首先，时间戳位于ID的最高位，保证新生成的ID比旧的ID大，在不同的毫秒内，时间戳肯定不一样。</span></p>
  <p data-lake-id="u307d0990" id="u307d0990"><span data-lake-id="u5a0734bd" id="u5a0734bd">​</span><br></p>
  <p data-lake-id="u3de07858" id="u3de07858"><span data-lake-id="u324d514f" id="u324d514f">其次，引入数据中心标识和机器标识，这两个标识位都是可以手动配置的，帮助业务来保证不同的数据中心和机器能生成不同的ID。</span></p>
  <p data-lake-id="u7e6137ef" id="u7e6137ef"><span data-lake-id="uf4097a29" id="uf4097a29">​</span><br></p>
  <p data-lake-id="u5b88622b" id="u5b88622b"><span data-lake-id="u033a9fce" id="u033a9fce">还有就是，引入序列号，用来解决同一毫秒内多次生成ID的问题，每次生成ID时序列号都会自增，因此不同的ID在序列号上有区别。</span></p>
  <p data-lake-id="u96779dcd" id="u96779dcd"><span data-lake-id="ufd3c3a30" id="ufd3c3a30">​</span><br></p>
  <p data-lake-id="u60fa0e79" id="u60fa0e79"><strong><span data-lake-id="u4f7685c9" id="u4f7685c9">所以，基于时间戳+数据中心标识+机器标识+序列号，就保证了在不同进程中主键的不重复，在相同进程中主键的有序性。</span></strong></p>
  <p data-lake-id="u29081398" id="u29081398"><span data-lake-id="uf58c63fb" id="uf58c63fb"><br></span><span data-lake-id="u36d36f5b" id="u36d36f5b">雪花算法之所以被广泛使用，主要是因为他有以下优点：</span></p>
  <ol list="ud1185d6d">
   <li fid="u2a091f98" data-lake-id="u9429a0a8" id="u9429a0a8"><span data-lake-id="u688ec849" id="u688ec849">高性能高可用：生成时不依赖于数据库，完全在内存中生成</span></li>
   <li fid="u2a091f98" data-lake-id="u98799c13" id="u98799c13"><span data-lake-id="u81edba02" id="u81edba02">高吞吐：每秒钟能生成数百万的自增 ID</span></li>
   <li fid="u2a091f98" data-lake-id="ufaa0d661" id="ufaa0d661"><span data-lake-id="u3326d770" id="u3326d770">ID 自增：在单个进程中，生成的ID是自增的，可以用作数据库主键做范围查询。但是需要注意的是，在集群中是没办法保证一定顺序递增的。</span></li>
  </ol>
  <p data-lake-id="u85baf036" id="u85baf036"><span data-lake-id="ub3e167f8" id="ub3e167f8">​</span><br></p>
  <p data-lake-id="udbe2d448" id="udbe2d448"><strong><span data-lake-id="u0619a2b0" id="u0619a2b0">SnowFlake 算法的缺点或者限制</span></strong><span data-lake-id="u3da31be8" id="u3da31be8">：</span></p>
  <p data-lake-id="u0b71fe49" id="u0b71fe49"><br></p>
  <p data-lake-id="u563cc287" id="u563cc287"><span data-lake-id="uc86146f6" id="uc86146f6">1、在Snowflake算法中，每个节点的机器ID和数据中心ID都是硬编码在代码中的，而且这些ID是全局唯一的。当某个节点出现故障或者需要扩容时，就需要更改其对应的机器ID或数据中心ID，但是这个过程比较麻烦，需要重新编译代码，重新部署系统。还有就是，如果某个节点的机器ID或数据中心ID被设置成了已经被分配的ID，那么就会出现重复的ID，这样会导致系统的错误和异常。</span></p>
  <p data-lake-id="u0900d2ed" id="u0900d2ed"><span data-lake-id="u2c94ac93" id="u2c94ac93" class="lake-fontsize-12" style="color: rgb(55, 65, 81); background-color: rgb(247, 247, 248)">​</span><br></p>
  <p data-lake-id="uf3b15276" id="uf3b15276"><span data-lake-id="u13ee800c" id="u13ee800c">2、Snowflake算法中，需要使用zookeeper来协调各个节点的ID生成，但是ZK的部署其实是有挺大的成本的，并且zookeeper本身也可能成为系统的瓶颈。</span></p>
  <p data-lake-id="ua9d6d001" id="ua9d6d001"><span data-lake-id="u6ea505a6" id="u6ea505a6">​</span><br></p>
  <p data-lake-id="uad199b6b" id="uad199b6b"><span data-lake-id="u95d74db0" id="u95d74db0">3、依赖于系统时间的一致性，如果系统时间被回拨，或者不一致，可能会造成 ID 重复。</span></p>
  <p data-lake-id="ua7f59d25" id="ua7f59d25"><span data-lake-id="uc73d969a" id="uc73d969a">​</span><br></p>
  <h1 data-lake-id="Jmyc8" id="Jmyc8"><span data-lake-id="udb387048" id="udb387048">扩展知识</span></h1>
  <p data-lake-id="uf47b824b" id="uf47b824b"><br></p>
  <h2 data-lake-id="xpbgr" id="xpbgr"><span data-lake-id="u794ac99e" id="u794ac99e">时钟回拨问题</span></h2>
  <p data-lake-id="ucc3dc7a5" id="ucc3dc7a5"><br></p>
  <p data-lake-id="u444b8f14" id="u444b8f14"><span data-lake-id="ub6e8f5c3" id="ub6e8f5c3">雪花算法使用时间戳作为生成ID的一部分，如果系统时钟回拨，可能会导致生成的ID重复。</span></p>
  <p data-lake-id="ud1199cf5" id="ud1199cf5"><span data-lake-id="u9b4eb39a" id="u9b4eb39a">​</span><br></p>
  <blockquote data-lake-id="u8f25a0ac" id="u8f25a0ac">
   <p data-lake-id="u797c2ab1" id="u797c2ab1"><span data-lake-id="u57907ada" id="u57907ada" style="color: rgb(0, 0, 0)">时间回拨是指系统在运行过程中，可能由于网络时间校准或者人工设置，导致系统时间主动或被动地跳回到过去的某个时间</span></p>
  </blockquote>
  <p data-lake-id="ufbbf5ad6" id="ufbbf5ad6"><br></p>
  <p data-lake-id="ucdd52ae6" id="ucdd52ae6"><span data-lake-id="u49222cf7" id="u49222cf7">一旦发生这种情况，简单粗暴的做法是抛异常，</span><strong><span data-lake-id="ud2de7663" id="ud2de7663">发现时钟回调了，就直接抛异常出来</span></strong><span data-lake-id="ua80dfe14" id="ua80dfe14">。另外还有一种做法就是</span><strong><span data-lake-id="u63a2294a" id="u63a2294a">发现时钟变小了，就拒绝ID生成请求</span></strong><span data-lake-id="ua08579ed" id="ua08579ed">，等到时钟恢复到上一次的ID生成时间点后，再开始生成新的ID。</span></p>
  <p data-lake-id="u441bc139" id="u441bc139"><span data-lake-id="uc75fd556" id="uc75fd556">​</span><br></p>
  <p data-lake-id="u559cedd7" id="u559cedd7"><strong><span data-lake-id="udd4a5a3b" id="udd4a5a3b" class="lake-fontsize-12" style="color: rgb(51, 51, 51)">美团 Leaf 引入了 Zookeeper 来解决时钟回拨问题</span></strong><span data-lake-id="u5faef4dd" id="u5faef4dd" class="lake-fontsize-12" style="color: rgb(51, 51, 51)">，其大致思路为：每个 Leaf 运行时定时向 zk 上报时间戳。每次 Leaf 服务启动时，先校验本机时间与上次发 ID 的时间，再校验与 zk 上所有节点的平均时间戳。如果任何一个阶段有异常，那么就启动失败报警。</span></p>
  <p data-lake-id="u53b5a25d" id="u53b5a25d"><span data-lake-id="u62bac046" id="u62bac046" class="lake-fontsize-12" style="color: rgb(51, 51, 51)">​</span><br></p>
  <p data-lake-id="u1207fd34" id="u1207fd34"><img src="https://cdn.nlark.com/yuque/0/2023/png/5378072/1678790894100-19a526b2-1d1d-42f2-b531-4c1920b41979.png?x-oss-process=image%2Fwatermark%2Ctype_d3F5LW1pY3JvaGVp%2Csize_14%2Ctext_SmF2YSA4IEd1IFA%3D%2Ccolor_FFFFFF%2Cshadow_50%2Ct_80%2Cg_se%2Cx_10%2Cy_10"></p>
  <p data-lake-id="u7f8a171b" id="u7f8a171b"><br></p>
  <p data-lake-id="u2bab87f9" id="u2bab87f9"><span data-lake-id="ubab86d3f" id="ubab86d3f">​</span><br></p>
  <p data-lake-id="ue6ead1e7" id="ue6ead1e7"><strong><span data-lake-id="u664cb29a" id="u664cb29a">百度的UidGenerator</span></strong><span data-lake-id="u3e1faaf3" id="u3e1faaf3">中有两种UidGenerator，其中DefautlUidGenerator使用了System.currentTimeMillis()获取时间与上一次时间比较，当发生时钟回拨时，抛出异常。而CachedUidGenerator使用是放弃了对机器的时间戳的强依赖，而是改用AtomicLong的incrementAndGet()来获取下一次时间，从而脱离了对服务器时间的依赖。</span></p>
  <p data-lake-id="u6c3818a6" id="u6c3818a6"><span data-lake-id="u271fe50b" id="u271fe50b"><br><br></span></p>
  <p data-lake-id="ua418efec" id="ua418efec"><span data-lake-id="uf067d44b" id="uf067d44b">​</span><br></p>
  <p data-lake-id="u37cf1897" id="u37cf1897"><span data-lake-id="ud3704868" id="ud3704868">​</span><br></p>
  <p data-lake-id="u1e8c550a" id="u1e8c550a"><span data-lake-id="u8bd965ef" id="u8bd965ef">​</span><br></p>
  <p data-lake-id="ub4ed5e31" id="ub4ed5e31"><span data-lake-id="u19423bda" id="u19423bda">​</span><br></p>
 </body>
</html>